package com.apkcore.bl;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class _146LRU缓存机制 {
    public static void main(String[] args) {

    }

    /**
     * 最近使用算法
     * 最近使用的就要插入到最前面，所以在添加或者访问后把数据插入到最前面
     * 由插入想到使用链表，o(1)时间复杂度
     * 而访问要想O(1)的时间复杂度来完成，那么必须使用hash访问
     * 由此我们可以大概推导出，这个题需要使用hash+双向链表来完成，而双向链表虚拟头尾节点来达到快速访问的目的
     */
    class LRUCache {

        private HashMap<Integer, Node> map;
        private Node headNode;
        private Node tailNode;
        private int capacity;
        private int count = 0;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            map = new HashMap<>(capacity);
            headNode = new Node();
            tailNode = new Node();
            headNode.nextNode = tailNode;
            tailNode.preNode = headNode;
        }

        public int get(int key) {
            Node node = map.get(key);
            if (node != null) {
                //删
                removeNode(node);
                //插
                addAfterHead(node);
                return node.value;
            } else {
                return -1;
            }
        }

        private void addAfterHead(Node node) {
            node.nextNode = headNode.nextNode;
            headNode.nextNode.preNode = node;

            headNode.nextNode = node;
            node.preNode = headNode;
        }

        private void removeNode(Node node) {
            node.nextNode.preNode = node.preNode;
            node.preNode.nextNode = node.nextNode;
        }

        public void put(int key, int value) {
            Node node = map.get(key);
            if (node != null) {
                node.value = value;
                removeNode(node);
            } else {
                ++count;
                if (count > capacity) {
//                if (map.size() == capacity) {
                    // 删除最近最少使用的key-value
                    removeNode(map.remove(tailNode.preNode.key));
                    count--;
                }
                map.put(key, node = new Node(key, value));
            }
            //插入到头节点后
            addAfterHead(node);
        }


        class Node {
            int key;
            int value;
            Node preNode;
            Node nextNode;

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }

            public Node() {
            }
        }
    }


    class LRUCache1 {

        private LinkedHashMap<Integer, Integer> cache;

        private int capacity;

        public LRUCache1(int capacity) {
            this.capacity = capacity;
            cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry eldest) {
                    return size() > capacity;
                }
            };
        }

        public int get(int key) {
            return cache.getOrDefault(key, -1);
        }

        public void put(int key, int value) {
            cache.put(key, value);
        }
    }
}
